#include<time.h>
#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>
#include <string.h>

void swap(int *a, int *b)    
{
   int tmp = *a;
      *a = *b;
      *b = tmp;
}

int * netherlands_flag(int* arr, int pl, int pr, int num)
{
    if (arr == NULL || (pr - pl) < 1) return NULL;
    int less = pl - 1;
    int more = pr + 1;
    int* res = (int*)malloc(2*sizeof(int));
    if (res == NULL) return NULL;
    memset(res, 0, 2*sizeof(int));
    while (pl < more) {
        if (arr[pl] < num) {
            swap(&arr[++less], &arr[pl++]);
        } else if (arr[pl] > num) {
            swap(&arr[pl], &arr[--more]);
        } else {
            pl++;
        }
    }
    res[0] = less + 1;
    res[1] = more - 1;

    return res;
}

//for test
int * generate_random_array(int max_size, int max_value, int *reallength) 
{
        srand((unsigned)time(NULL));
        int length = rand() % (max_size + 1); //生成0~maxSize+1的随机数
        *reallength = length;
        int *arr = (int*)malloc(length * sizeof(int));  
        for (int i = 0; i < length; i++) {
            arr[i] = (rand() % (max_value + 1)) - (rand() % max_value);
//            arr[i] = rand() % (max_value + 1);
        }
        return arr;
}
//for test
void print_array(int arr[], int length) {
    if (length == 0) {
        return;
    }
    for (int i = 0; i < length; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");
}

void main(int argc, char **argv) {
    int max_size = 150;
    int max_value = 180;
    int *arr1 = NULL;
    int reallength = 0;
    arr1 = generate_random_array(max_size, max_value, &reallength);
    print_array(arr1, reallength);
    int* res1 = netherlands_flag(arr1, 0, reallength-1, 50);
    print_array(arr1, reallength);
    if (res1 != NULL) print_array(res1, 2);
    if (arr1 != NULL || res1 != NULL) {
        free(arr1);
        free(res1);
    }
}
